This invention is generally related to computer systems and more particularly to techniques for avoiding deadlock and livelock when performing bus transactions across a bridge.
Computer systems use a bridge between two buses to allow devices on one bus to communicate with devices on the other bus. FIG. 1 shows such a conventional computer system 102. The system 102 has one or more processors 104 coupled to a host bus 105. The host bus 105 and the processor 104 may be pipelined. A main memory 112 normally comprising Dynamic Random Access Memory (DRAM) is provided for storing programs and data used by the processor 104 and by peripheral devices. The memory 112 can be accessed by the processor 104 and by other devices via a host bridge 108. To speed program execution by minimizing accesses to the memory 112, a cache 114 (which may be internal to the processor 104) is coupled to the host bus 105.
The host bridge 108 also handles transactions between devices on the host bus 105 and those on a system bus 116. The system bus 116 may be one which complies with the currently popular Peripheral Components Interconnect (PCI) Specification, Rev. 2.1, Jun. 1, 1995. A number of slots are provided on the system bus 116 to receive PCI devices such as mass storage controller cards and network interface cards. The host bridge 108 also supports transactions between a graphics device 122 and a device on the system bus 116.
The PCI-based example in FIG. 2, will be used to demonstrate some problems with the conventional system 102. Read and write transactions across the bridge 108 consist of several access cycles. For instance, posted write transactions involve at least two access cycles. The first cycle is on the initiating side of the bridge (e.g., on the host bus 105) during which a transaction request packet is accepted by the bridge and placed in an in-order queue (IOQ)222. Thereafter, the first cycle may be completed by transferring the request packet and its associated data to a host bridge PCI outbound pipe 226 (PCI0_OUT) that operates in a first in first out (FIFO) manner. Once the first access cycle is completed, a second access cycle may begin on the system (PCI compliant) bus 116 once the packet reaches the head of PCI0_OUT, to transfer the associated data to a target on the system bus 116. Accesses to the main memory 112 have the additional requirement that the cache 114 be checked for the most recent copy of the data being accessed. For instance, a write to a line in main memory 112 requires invalidating or updating the corresponding line in the cache 114. These data coherency operations require the host bus to be available to check the cache 114.
Modern computer systems operating as network servers or workstations featuring the architecture of FIG. 1 and FIG. 2 are expected to handle a large number of transactions that cross a bridge. When one side of the bridge is subjected to a relatively greater number of transactions than another side, the large number of transactions have the potential to create a deadlock. This is a very serious and usually fatal condition in that the system must normally be shut down if deadlock occurs.
In FIG. 2, deadlock may occur when the cache 114 must be checked as part of an upstream transaction PMW-4 which is at the head of a host bridge PCI inbound pipe (PCI0_IN) which is full. The host bus 105 is not available due to an already pending access cycle for a downstream transaction PW-3. The pending access cycle for PW-3 is stalled and cannot be completed until there is space in PCI0_OUT to accept the transaction request and associated data packets. However, PCI0_OUT has also become full, perhaps because target devices on the PCI bus 116 cannot drain PCI0_OUT as quickly as transactions from the IOQ 222 and a host bridge PCI inbound pipe PCI1_IN are enqueued. This may be because a downstream transaction PW-1 directed at the device 232 on the PCI bus 116 cannot be completed until an upstream memory transaction PMW-2 in the same device has completed. This is an example of an outbound-inbound dependency that certain older peripheral devices such as legacy devices exhibit, where an inbound request cannot be accepted (even though the inbound pipe PCI2_IN is empty) until an existing transaction PMW-2 at the head of its outbound pipe PCI2_OUT has been completed. There are various other situations that pose the inbound/outbound dependency. In all of these situations, since the host bus 105 is not available, PCI0_IN in the bridge 108 cannot be drained and remains full, such that PMW-2 is refused service. Therefore, there is a deadlock as the PW-3 cycle is stuck on the host bus 105 with no data transfer occurring.
One way to avoid the above-described deadlock condition is to reconfigure the peripheral device 232 to eliminate its inbound-outbound dependency to allow PW-1 to proceed before PMW-2 has completed. However, such a technique would require manufacturers to significantly modify current and older peripheral devices, thus substantially increasing the cost of the computer system. Therefore, there is a need for a technique of avoiding deadlocks that does not require expensive modifications in peripheral devices.